Since its inception, telephony has depended upon the use of pairs of copper wire, also referred to as “copper loop” or just “loop”, as the main local area data transmission medium. Although cable, fiber optics, and wireless links like microwave, satellite, and cellular telephones have greatly enhanced communication access for the subscriber, they do not yet replace copper as the main transmission medium for hundreds of millions of individual applications. The existing “copper loop” infrastructure in place today represents an enormous investment in resource and time.
Modern telephony requires connect, disconnect or modification of hundreds of thousands of services daily. Examples of such service changes are, connecting a new phone line for a subscriber's home, providing additional phone lines for a business, adding DSL or other high speed data link to an existing subscriber service, re-routing a phone line to bypass a faulty line, or disconnecting a phone service. Historically, when a subscriber requested a change in service, a repair or change order was generated to instruct a technician to make the required changes. Other applications can have similar needs.
In some regards, connections may involve physical interconnects required to transmit the intended data or information. Connections may also be abstract in that they are internal to a computer, software manifested, or the like. Such interconnects may be distinct from the switching process associated with making phone calls. Dialing services may be provided in a switching office by switching equipment perhaps even premises equipment which may perform the functions of establishing and releasing connections on a per call basis between two of more circuits, services or communications systems. Router services and connectivities such as may be found in internal computer architectures may be included as well. Dialing services may even rely on an infrastructure of existing transmission media and interconnects, including copper pairs and fiber optics, perhaps such as described in the preceding paragraphs to perform their function. Abstract signal pathways can rely on real or virtual switching (which may not be manifestly visualized) to direct the appropriate communication.
With technology advances demanding ever increasing flexibility and connection speeds, installation, maintenance and upgrades of “loop” service to residences and industry is becoming an increasing problem. Similarly the challenge of internal computer communication among a variety of signal sources needs to be addressed. Having a technician test and hand wire connects and disconnects is labor intensive, costly, error prone, and can result in poor documentation records, poor quality, and low customer satisfaction. Documentation and billing of such services and changes are resource and time demanding tasks with record accuracy nigh unto impossible. As a result, the telephone industry has considered automated loop management systems, LMS. In some regards it has been desired that these systems be able to handle “loop” service for up to 40,000+ subscribers. These systems may be desired to automate “copper loop” related tasks that would otherwise be performed by the technician with the goal of reducing cost and overhead and increased documentation accuracy of loop management. An LMS may consist of a hardware component, perhaps a “switching fabric”, and a software or other automated component to control the fabric and interface with a system administrator. Together they may be desired to provide complete automatic connect function under administrator/operator direction.
While a detailed description of the construction and operation of an LMS is unnecessary for this disclosure, some key characteristics and elements desired in a “switching fabric” may be helpful to understand the nature of the herein described invention. True arbitrary, any-to-any, non-blocking, fault tolerant, automated loop management systems that can support 100% fill in loop service for as many as forty thousand plus subscribers, as desired by the telephone industry, are either unavailable or largely prohibitively costly and unmanageable. Matrix switches, such as devices that include an array of switches or cross-points arranged and interconnected where a node, a signal or pair of lines, of an input set of nodes can be connected to a chosen node of an output set of output nodes such that a unique signal path is created through the array can be difficult to work with. For example a “simple” array, such as a simple one stage classic array, is shown in FIG. 2. This is inherently non-redundant because there is only one unique path for each selected connection. Redundancy, such as having one or more ‘backup’ systems or pathway available in case of the failure of the chosen system or pathway, is desired. In a matrix switch this can involve having multiple equally valid paths between the input and output nodes to provide the desired connections regardless of individual faults or blocked paths. Providing redundancy could require many additional parallel paths. Furthermore, composition of a large one stage, any-to-any matrix switch (one of the most traditional designs) is often impractical because, as the number of input (perhaps considered feeder pairs in some applications) and output (perhaps considered distribution pairs in some applications) increases, the number of array elements grows exponentially. For example, a 4,000 port array allowing 2,000 feeder pairs to be connected arbitrarily to 2,000 distribution pairs may require 4,000,000 cross-points, or 2,000 cross-points per connection. Even at $0.50 per cross-point this is $1000 per connected loop. A 20,000 by 20,000 array may require four hundred million cross-points.
A dominant cost factor in the construction of such fabrics may even be the number of cross-points in the fabric. All other costs may scale with the number of cross-points required for the final solution. There exist many schemes with various different topologies that provide array element count reduction. Banyan, Omega, n-Cube, Benes and Clos structures exist, for example. These have strengths and weaknesses but most are, to varying degrees, useful devices. One topology of interest may be the Clos Network.
In 1952 Charles Clos published a paper at Bell Labs titled “A Study of Non-Blocking Switching Networks” [The Bell Systems Technical Journal 1953, vol. 32 no. 2 pp. 406-424.] Clos's work provided a tops-down approach to reduced cross-point switching network design (e.g., given a desired array size, applying the Clos method may enhance the underlying array structure.) From some perspectives, his work has formed a basis for reduced cross-point switching systems ever since, however; the present invention shows considerable improvement was not understood or appreciated from this type of understanding. Similarly, there are specific variations of the Clos Network that have acquired identifiable and unique names. For example the Benes Networks can be viewed as a Clos Network that uses successive levels of recursion with a binary (2) radix sub-array size for all arrays. The present invention shows that this, too, failed to appreciate the types of advances that could yet be achieved.
To some degree, Clos may be interpreted as showing how a ‘Simple’ N by N array can be decomposed and reassembled as a three stage set of smaller sub-arrays such that the total number of cross-points can be significantly reduced. Further this rearrangement may also provide multiple possible paths for each connection and also redundancy and fault tolerance as desired by the telephone industry among others. Clos's theory may apply to symmetrical, X by X, and non symmetrical, or asymmetric, X by Y, arrays. As an example, see FIG. 3, depicting a general form of the classic Clos three stage network in a symmetrical or square array. This array can be understood as demonstrating how a ‘simple’ N by N array can be decomposed and reassembled as a three stage set of smaller sub-arrays such that the total number of cross-points can be significantly reduced. Further this rearrangement provides multiple possible paths for each connection and therefore provides redundancy and fault tolerance as desired by the telephone industry. For an array with N by N inputs, the sub arrays are specified to be of size n where N≈n2. The parameters of interest are n, m, and r, with N=n*r inputs and N=n*r outputs, where n is the number of inputs to each outer, left and right, sub array, r is the number of outside or exterior sub arrays required to provide N inputs and m is the number of center arrays required to accept all the inputs from the side arrays. It can be shown that m must be equal to or greater than n to provide a non-blocking array capable of 100% fill.
To illustrate the concept, we have chosen the case where m=n. Using our example of the 4,000 port array and applying Clos's technique for a three stage array to decompose the matrix into sub-arrays with 2000=n*r, and n=m=40 and r=50 and then recombining them results in a complete solution requiring only 260,000 cross-points, or 130 cross-connects per connection. This is a savings of 93.5% or 3,740,000 cross-points.
In spite of this impact, it remains a fact that this technique alone still does not provide enough reduction in array cross-point count to make the very large arrays desired by the telephone industry practical. However, by applying recursion to the Clos Network, further decomposition and recombination is possible. FIG. 4 depicts a level one recursive Clos network. It can be shown that such techniques may provide significant additional cross connect savings and that the application of recursion may even be more effective on very large arrays.
Again using our exemplary 4,000 port array, and setting n=8 and r=250 for the first decomposition and then using recursion on r such that r=n′*r′ to obtain n′=10 and r′=25 our example yields 122,000 cross-points. This is an additional savings of about 3.5% or another 138,000 cross-points for a total savings of almost 97%. Using n=5 and r=400 for the first recombination and then using recursion to obtain n′=5 and r′=80 and then using recursion again to obtain n″=8 and r″=10 our example yields 92,000 cross-points. This saves another 0.75%, and an additional 30,000 cross-points for a total savings of 97.7%.
Following the recursive examples, however, it is a fact that application of successive levels of recursion provides rapidly diminishing additional returns. For very large arrays, using multiple levels of recursion could still provide enough reduction in overall system size and cost to make the switching fabrics required by the telephone industry more feasible. There is, however, one more obstacle to overcome. The cross-point array configuration in which we chose m=n, to provide the minimum number of cross-points as used in our example is not strictly non-blocking Although there are multiple paths for each connection and all connections can theoretically be made allowing 100% fill, choosing the wrong path for any given connection may block all paths for a future connection. Such a network may be called conditionally or perhaps rearrangeable “non-blocking”. Rearrangeable “non-blocking” infers that by rearranging the chosen paths, all paths can be completed (with varying degrees of and attempts at rearrangement) and this can be shown to be true for the network of FIG. 3 or FIG. 4. Unfortunately, because of the unanticipatable nature of the connections, there has been no known way to predict in advance which connection paths will not block the paths of future connections. Breaking a connection to move it to another path to make room for a new connection also may be disruptive to subscriber services and therefore perhaps generally unacceptable.
As stated in the previous paragraph, the array of FIG. 3, in which we chose m=n, is only conditionally “non-blocking”. To make it unconditionally or strictly “non-blocking” and overcome potential service disruptions, additional center sub arrays could be provided and additional cross-points added to both side arrays. While the math shows that a network of any size (e.g. N by N) as illustrated in FIG. 3 with the minimum paths required for a conditionally “non-blocking” array where n=N/r is n, that is m=n, as stated for our simplified form of the network, the unconditionally “non-blocking” array, as proposed by Clos, requires m=2n−1. Therefore, even for relatively small sub arrays as in our example where n=40, the unconditionally “non-blocking” cross-point count is nearly double that computed in our example, i.e. m=79. For large arrays this doubles the size, complexity and cost of the three stage system and the application of recursion compounds the problem. Thus, a switching fabric based on the Clos Network desired by the telephone industry becomes much less feasible.
Going back to our example of the 4,000 port array and applying Clos's technique to obtain an unconditionally “non-blocking” matrix with 2000=n*r, and n=40, m=(2n−1)=79 and r=50 results in a solution requiring 513,500 cross-points for a savings of only about 87.2% or 3,486,500 cross-points. Applying one level of recursion, as in our example above, we get 380,625 cross-points, for an additional savings of only about 3.3% or 132,875 cross-points and a total savings of 90.48%. Applying additional levels of recursion are unproductive as the cross-point count increases. Thus a non-blocking array remains largely uneconomic.
As can be seen from the discussion so far, the problems of network switching fabric construction, its complexity and cost as faced by the telephone industry has been a significant impediment to “loop” automation. Some of the prior art is instructive in gaining an understanding of the nature of the problems and shortcomings of the solutions provided. Some prior inventions include: U.S. Pat. No. 3,993,871 to Hjortendal, et al. Nov. 23, 1976, U.S. Pat. No. 4,088,845 to Lalanne, et al. May 9, 1978, U.S. Pat. No. 4,231,017 to Kiriyama, et al. Oct. 28, 1980, and U.S. Pat. No. 6,914,902 to Ayandeh. Jul. 5, 2005. To some extent, these focused on how to construct matrices and the support structures required to implement them and how to control the cross-point switches. They had little impact on reducing cross connect element count. For example, U.S. Pat. No. 5,644,115 to Knauer describes a test instrument switching matrix that is a simple N by M matrix. It involves specific composition and construction of the arrays. For the most part these problems have been solved by advances in electronics like the fabrication of miniature latching relays, MEMS technology, optical switches and the use of large scale circuit integration. Additional recent inventions include: U.S. Pat. No. 4,394,541 to Seiden Jul. 19, 1983, U.S. Pat. No. 6,696,917 to Heitner, et al. Feb. 24, 2004, U.S. Pat. No. 6,914,902 to Lu, May 31, 2005, and even the current inventor's own US Patent Publication US20040017805, to Smith, Robert B., Jan. 29, 2004.
It is interesting to observe the mind set in these inventions. Most assumed that the wisdom of related prior art was to some extent infallible. For example, U.S. Pat. No. 6,696,917 to Heitner, et al state the objective of using binary, 2n, for array sizes states “it is more advantageous to employ square crossbar switches preferably sized in binary increments as such devices are readily available in the industry.” Such notions are clearly the result of the computer age and the proliferation of computer technology which permeates the entire communications industry.
US Patent Publication 20040017805, to Smith, Robert B., Jan. 29, 2004 illustrates interesting characteristics. An understanding of the value of recursion is demonstrated. Note that the sub arrays for the smaller arrays are based on binary, 2n, size increments as demonstrated by prior art. Use of 5×5 arrays is introduced only to illustrate the possibility of providing an assembled array size of exactly 500 by 500 ports. As it turns out, using only 4 by 4 and 8 by 8 arrays for a final array size of 512 by 512 would have been more efficient in providing 500 by 500 ports and would have had more redundancy, however, even the present inventor did not appreciate this until perhaps almost serendipitously realizing the fundamental concepts that lead to the present invention.
A drawback to even the present inventor's US Patent Application 20040017805, to Smith, Robert B. disclosure, however, is that it does not overcome the conditionally non-blocking problem illustrated above. The cross-point array configuration illustrated in US Patent Publication 20040017805, to Smith, Robert B. et al chose m=n, to provide the minimum number of cross-points. As discussed above in our example, an array based on m=n is not strictly “non-blocking” and therefore cannot provide 100% fill without substantial service interruption during routing of new connections.
To some extent this group of disclosures focused on modifying the complexity and size of switching fabrics and/or control in novel, but not always in practical ways from the present perspective. U.S. Pat. No. 4,394,541 to Seiden recognized the added size and cost of implementing the strictly “non-blocking” Clos network and therefore partially overcame the conditionally or rearrangeable “non-blocking” problem by placing “mid stage links” or additional cross bar elements in the center sub-arrays of the three stage array to allow linking a blocked path to an adjacent mid stage array to complete the path. While this technique can reduce the number of blocked paths, it is not sufficient to provide a guarantee of 100% fill as would be required to utilize all input and outputs of the fabric, nor does it address the need for additional outer stage links around the inner stages for the recursive solution. The scheme as presented may not work for five and higher stage Clos networks. The addition of many mid stage links are required to prevent all potential blocking and therefore the method appears not very useful from the present perspective. It does not adequately address the problem of ongoing service changes. When a subscriber service is terminated, the associated feeder and distribution pairs become available for other, different, associations. The scheme of U.S. Pat. No. 4,394,541 does not allow reassignment without disruption of other services, especially as the fabric nears 100% fill.
U.S. Pat. No. 6,696,917 to Heitner, et al presented a “Folded Clos Architecture” that attempted to minimize what is perceived as wasted input and outputs in the left and right sub-arrays. Referring again to the sample of FIG. 3, it attempts to more efficiently use “standard” square arrays to implement a strictly “non-blocking” structure. This was accomplished by folding the rectangular, n by m, input and output arrays into a combined square array. Unfortunately this folding wasted many cross-points in the resulting square array. The wasted cross-points can be computed for the array illustrated in the disclosure. Two 8 by 15 arrays require 240 cross-points (2*8*15=240), while the combined 23 by 23 array requires 529 cross-points (1*23*23=529). In this case conserving unused inputs and outputs requires a considerable waste of cross-points. Also in the illustrations, the individual center arrays, whose size was chosen according to the Clos method, may even be too small to be as efficient as desired. In this manner the Clos method might appear not as useful as possible to reduce total cost or size. In fact, total cost may go up because of the dominant influence of cross-points on overall cost. It is significant to note that reduced cross-point count was not the goal of that invention.
Regardless of existing methods and related theory and emerging cross-point technology, what is really needed is a significant change in the structures and procedures for switching fabrics in order to further reduce array size and better utilize array element properties. The new structures may also take full advantage of existing technology. Both these new structures and these new methods may apply to methods and practices in the field of switching networks.